package com.leecode;

/**
 * 31. 下一个排列
 *
 * 实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
 *
 * 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
 *
 * 必须原地修改，只允许使用额外常数空间。
 *
 * 以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
 * 1,2,3 → 1,3,2
 * 3,2,1 → 1,2,3
 * 1,1,5 → 1,5,1
 */
public class Leet31 {
	public static void main(String[] args) {
		new Leet31().nextPermutation(new int[]{4,2,0,2,3,2,0});
	}

	/**
	 * 98%,82%,我
	 * 考点:找到"最合适的最低位"!!
	 * 如:165000
	 * 6问后面的,有没有比6大的?没有!下一位
	 * 1问后面的,有没有比1大的,有!最低位index确定,是"1在的位置",但不能马上交换,要从"比1大的"集合里找出最小的index
	 * 561000,剩下就是61000搞出min
	 */
	public void nextPermutation(int[] nums) {
		if(nums==null || nums.length<2)return;

		int moveE=nums.length-1;
		boolean flag=false;
		int index=-1;
		int maxMinIndex=-1;//比当前大的有个集合,从集合中选最小的
		h:
		for (int a = moveE-1; a >= 0; a--) {//从倒数第二位开始,询问"后面的"有没有比自己大的?
//			for (int b = a - 1; b >= 0; b--) {//交换的思路就错了
//				if (nums[a] > nums[b]) {
//					swap(nums,a,b);
//					index=b;
//					flag=true;
//					break h;
//				}
//			}

			for(int b=a+1;b<nums.length;b++){
				if(nums[b]>nums[a]){//从倒数第二位开始,询问"后面的"有没有比自己大的?
					flag=true;
					index=a;
					if(maxMinIndex==-1){
						maxMinIndex=b;
					}else{
						if(nums[b]<nums[maxMinIndex]){
							maxMinIndex=b;
						}
					}
				}
			}

			if(flag){
				swap(nums,index,maxMinIndex);
				break h;
			}
		}

		if(flag){
			for(int a=index+1;a<nums.length;a++){
				for (int b = a + 1; b < nums.length; b++) {
					if(nums[b]<nums[a]){
						swap(nums,a,b);
					}
				}
			}
		}else{
			int b=0,e=nums.length-1;
			while(b<e){
				swap(nums,b++,e--);
			}
		}
	}
	public  void swap(int[] arr, int a, int b){
		int temp=arr[a];
		arr[a]=arr[b];
		arr[b]=temp;
	}

}
